For traffic studies in communication systems, it has been fairly standard to use queueing models that assume that customer interarrival intervals and service times are independent, each being modelled as a renewal process. These standard models are easy to simulate and under suitable assumptions are even analytically tractable.
Unfortunately, they are very often poor models of real-life systems where correlations do exist, for example, bursty interval streams are typical examples of high correlation. Additionally, video signals include considerable correlation from line to line and frame to frame. In practice, there is a dramatic degradation of performance induced by increasing correlations. These correlations when suitably accounted for, can yield improved system design. In any event, it is advantageous to include known correlations when modeling real systems.
Typically, simulations have used a pseudo-random number generator to generate real sequences which model independent identically distributed (iid) uniform variates. Simulations for generating dependent sequences with specific correlations have received less attention.
A preferred generation method for dependent sequences of random variates should satisfy the following criteria:
a) Period: the generated sequence should have a reasonably long period; in particular, if the correlated sequence is generated by transforming an underlying random number sequence, then the period of the two sequences should be comparable.
b) Complexity: the time and space complexity required to implement the method on a computer should be reasonable functions of their counterparts in the underlying random number generator. Space complexity is rarely the issue, so one usually wants fast methods, especially when long sequences are required.
c) Coverage: the full range of theoretic correlations, that is (-1, 1), should be attainable by a suitable adjustment of the method's parameters. Thus, if .rho..sub.min and .rho..sub.max are the extremal lag-1 autocorrelations, it is required that correlation in the range (.rho..sub.min, .rho..sub.max) be attainable. The endpoints are exempt since they may only be attained by degenerate methods.
d) Behavior: a method should generate a wide range of sample path behaviors as a function of its parameters.
The autocorrelation structure .rho..sub.n of a real random stationary sequence {X.sub.n } with finite second moment, is a measure of (linear) dependence captured by the sequence ##EQU1## of the lag-n correlation coefficients, where X.sub.n are the random variables, and where .mu..sub.x is the common mean and .sigma..sub.x.sup.2 is the common variance of the X.sub.n.
Various methods that have been used hitherto to generate correlated variates with uniform marginals can be broadly classified into three approaches (the goal is always to generate a stationary sequence {X.sub.n } with a marginal distribution function F).
Approach 1: Generate X.sub.0 .about.F and then continue recursively, generating X.sub.n+1 from X.sub.n through some autoregressive scheme which is closed under F (i.e., preserves F). This approach is the most popular one. It enjoys the advantage that the attendant autocorrelation function is typically very easy to derive. On the other hand, this approach is ad hoc in the sense that one needs to devise a separate autoregressive scheme for each F. For some families of distributions, finding the appropriate autoregressive scheme can be quite daunting.
Approach 2: Fix a tractable marginal distribution F* (normal is a typical choice), and generate the corresponding sequence {X.sub.n.sup.* }, with an autoregressive scheme closed under F*. Then, the sequence {F*(X.sub.n.sup.*)} is uniform and the target sequence {X.sub.n } is obtained via the inversion method, i.e., X.sub.n =F.sup.-1 (F*(X.sub.n.sup.*)). Here the autocorrelation structure has been transformed twice: once by F* and once by F.sup.-1. Nevertheless, the autocorrelation function of {X.sub.n.sup.* } can be computed in principle, though numerical difficulties could be presented by certain F. This approach is more general than the previous one, but it shifts the difficulties to the numerical calculation of the transformed autocorrelation structure.
Approach 3: This is a special case of the previous approach when F* is already chosen to be uniform, thereby obviating the first transformation in Approach 2. Nevertheless, the major simplication brought about by this choice of F* merits viewing it as a separate approach.
For our novel technique, we shall follow Approach 3, and so we henceforth focus on generation methods for correlated uniform sequences {U.sub.n } and on their autocorrelation structure.
A general though unspecific procedure to generate a c.i.d. (correlated identically distributed) sequence of random variables {X.sub.n } is to take an i.i.d. (independent identically distributed) Uniform (0,1) sequence {Z.sub.n } (generated approximately on a computer via a pseudo-random number generator), and transform it into a correlated uniform sequence {U.sub.n }. If a correlated sequence with another (non-uniform) marginal distribution is desired, the sequence {U.sub.n } may be further transformed, say by transformations D.sub.n , yielding the target sequence {X.sub.n }, where X.sub.n =D.sub.n (U.sub.n). For historical reasons the D.sub.n shall be referred herein as distortions. Typically, D.sub.n will implement an inversion method; that is D.sub.n =F.sub.n.sup.-1 where F.sub.n is the distribution function of the X.sub.n. To keep notation simple, we shall henceforth deal with stationary sequences with a common distortion D. Note, however, that D transforms the autocovariance structure, i.e., it maps the autocovariance function of {U.sub.n } EQU .PSI..sub.U (.tau.)=Cov[U.sub.0, U.sub..tau. ]=E[U.sub.0 U.sub..tau. -1/4, .tau.=0, 1, (1.1)
to the autocovariance function of {X.sub.n } EQU .PSI..sub.X (.tau.)=Cov[X.sub.0, X.sub..tau. ]=E[D(U.sub.0)D(U.sub..tau.)]-.mu..sub.X.sup.2, .tau.=0, 1,(1.2)
where .mu..sub.X is the common mean of the X.sub.n. In particular, .PSI..sub.X (0)=.sigma..sub.X.sup.2 where .sigma..sub.X.sup.2 is the common variance of the X.sub.n (assumed finite throughout the discussion).
In practice, constraints on a correlated sequence are stated in terms of the target sequence {X.sub.n }. These requirements will usually include the form of the marginal distribution of {X.sub.n } as well as the first few autocorrelations. The need is to devise an auxiliary uniform sequence {U.sub.n } and implement it on a computer such that transforming each U.sub.n to X.sub.n via D would comply with the prescribed constraints on {X.sub.n }. The term "controlling the autocorrelations" refers to an ability to satisfy autocovariance constraints. Thus, one way to control autocorrelations is to devise generation methods of uniform sequences {U.sub.n }, derive their autocovariance function (1.1), and then proceed to find the mapping .PSI..sub.U .fwdarw..PSI..sub.X (induced by D) and its inverse mapping .PSI..sub.X .fwdarw..PSI..sub.U.
The literature contains considerable work on generating target sequences {X.sub.n } directly. Such methods are tailored to a specific target distribution and have easily derived autocorrelation functions. However, they may require more than one transformation to conveniently generate arbitrary marginals (the first transformation being the distribution function and yielding a uniform variate). Since one usually needs to follow the uniform distribution route, working with uniform sequences is much desired. The generation problem of correlated uniform sequences {U.sub.n } was addressed by a number of workers in the prior art. For example, workers have proposed minification (moving minimum) and maxification (moving maximum) processes. The present invention employs a new method for generating Markovian sequences of random variables with uniform marginals.